package LimitedTimeGame.Day_0211;

/**
 * @author zxc
 * @date 2023/02/11 10:55
 **/

import java.util.Arrays;

/**
 * 题目 ：三角形的最大周长
 * 题目详述 ：
 * 给定由一些正数（代表长度）组成的数组 nums ，返回 由其中三个长度组成的、面积不为零的三角形的最大周长 。
 * 如果不能形成任何面积不为零的三角形，返回 0。
 *
 * 提示：
 * 3 <= nums.length <= 104
 * 1 <= nums[i] <= 106
 *
 */
public class LargestPerimeter {
    /**
     * 思路 ：
     * （1）对于nums数组进行排序;（从小到大）
     * （2）固定住nums数组中最大元素（从大到小）作为三角形的最大边
     * （3）然后取三角形第二大的边nums[i]，再取三角形最大边的前一个nums[i-1]作为最小边
     *  ===》 若是构不成三角形的话，那么就算最小边继续向前取也是没有意义的;
     *
     * @param nums
     * @return
     */
    public int largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        int len = nums.length;
        for(int i = len - 1 ;i > 1 ;i--){
            int a = nums[i];
            int b = nums[i - 1];
            int c = nums[i - 2];
            // 由于a作为三角形最大边，即代表了a + c > b && a + b > c是必然成立的;
            // 即，b = nums[i - 1]为仅次于最大边a的第二大边;c = nums[i - 2]为仅次于最大边a的第三大边;
            // ===> 即，若是b + c <= a的话，那么nums数组中，就不存在能够大于 最大边a的两条边，从而组成三角形;
            if(b + c > a){
                // 即，找到的第一个能够构成三角形的三条边，即为能构成的最大三角形;
                return a + b + c;
            }
        }
        return 0;
    }
}
